package leetcode_2301_2400;

public class LeeCode_2302 {
    public static void main(String[] args) {
        System.out.println(countSubarrays(new int[]{9,5,3,8,4,7,2,7,4,5,4,9,1,4,8,10,8,10,4,7}, 4));
//        System.out.println(countSubarrays(new int[]{2, 1, 4, 3, 5}, 10));
    }
    private static long countSubarrays(int[] nums, long k) {
        int n = nums.length;
        long[] sums = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i  - 1];
        }
        long ans = 0;
        for (int i = 0; i < n; i++) {
            int index = search(sums, i, k);
            if (index == -1)
                continue;
            ans += index - i;
        }
        return ans;
    }
    private static int search(long[] sums, int start, long k){
        int l = start + 1, r = sums.length - 1;
        while (l < r){
            int m = (l + r + 1) >> 1;
            long sum = (sums[m] - sums[start]) * (m - start);
            if (sum >= k){
                r = m - 1;
            }else {
                l = m;
            }
        }
        long sum = (sums[l] - sums[start]) * (l - start);
        return sum < k ? l : -1;
    }
}